package com.captain.lc.动态规划;

/**
 * Des:
 * 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
 * <p>
 * 回文字符串 是正着读和倒过来读一样的字符串。
 * <p>
 * 子字符串 是字符串中的由连续字符组成的一个序列。
 * <p>
 * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
 *
 * @author XL
 * @Date 2021/10/25 15:32
 */
public class CountSubstrings647 {

    public int countSubstrings(String s) {
        //解题思路,纵向遍历,确保dp[i +1][j -1]是没有问题的
        //[][][]
        //[][][]
        //[][][]
        if (s == null || s.length() < 1) return 0;
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int count = 0;
        //按照列来遍历
        for (int j = 0; j < len; j++) {
            // i -- j的范围内
            //第一次就是 第一列第一行
            for (int i = 0; i <= j; i++) {
                if (s.charAt(j) == s.charAt(i)) {
                    //例如 a a , 肯定是
                    if (j - i < 3) {
                        dp[i][j] = true;
                        count++;
                    } else {
                        //往里缩进 i + 1 ,j -1
                        //往前一列, 往下一列
                        dp[i][j] = dp[i + 1][j - 1];
                        if (dp[i][j]) count++;
                    }
                } else {
                    dp[i][j] = false;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(new CountSubstrings647().countSubstrings("aaaaa"));
    }

}
